package linked_list

import (
	"errors"
	"fmt"
	"strconv"
	"strings"
)

var (
	ErrIndexIllegal = errors.New("index out of range")
	ErrItemNil      = errors.New("added item can't be nil")
)

type LinkedList struct {
	size int
	// virtual node
	dummyNode *node
	lastNode  *node
	curNode   *node
}

func (ll *LinkedList) Next() interface{} {
	if ll.curNode == nil {
		ll.curNode = ll.dummyNode
	}
	ll.curNode = ll.curNode.next
	return ll.curNode.val
}

func (ll *LinkedList) HasNext() bool {
	return ll.curNode != ll.lastNode
}

func NewLinkedList(capacity int) *LinkedList {
	return &LinkedList{
		dummyNode: &node{
			prev: nil,
			next: nil,
			val:  nil,
		},
	}
}

type node struct {
	prev *node
	next *node
	// val must can be sortable
	val interface{}
}

func (ll *LinkedList) Add(item interface{}) error {
	if item == nil {
		return ErrItemNil
	}
	tmpNode := ll.dummyNode
	for i := 0; i < ll.size; i++ {
		tmpNode = tmpNode.next
	}
	addedNode := &node{
		prev: tmpNode,
		next: nil,
		val:  item,
	}
	tmpNode.next = addedNode
	ll.lastNode = addedNode
	ll.size++
	return nil
}

func (ll *LinkedList) Size() int {
	return ll.size
}

// Find is find the item at position idx
func (ll *LinkedList) Find(idx int) (interface{}, error) {
	if err := ll.preCheckIndex(idx); err != nil {
		return nil, err
	}
	if idx > ll.size/2 {
		tmpNode := ll.lastNode
		for i := ll.size - 1; i > idx+1; i-- {
			tmpNode = tmpNode.prev
		}
		return tmpNode.val, nil
	} else {
		tmpNode := ll.dummyNode
		for i := 0; i < idx; i++ {
			tmpNode = tmpNode.next
		}
		return tmpNode.val, nil
	}
}

func (ll *LinkedList) Last() interface{} {
	if ll.dummyNode.next == nil {
		return nil
	}
	return ll.lastNode.val
}

func (ll *LinkedList) preCheckIndex(idx int) error {
	if idx < 0 || idx > ll.size {
		return ErrIndexIllegal
	}
	return nil
}

func (ll *LinkedList) String() string {
	builder := strings.Builder{}
	tmpNode := ll.dummyNode
	builder.WriteString(fmt.Sprintf("size: %d\n", ll.size))
	builder.WriteString("content: ")
	for i := 0; i < ll.size; i++ {
		if i != 0 {
			builder.WriteString("->")
		}
		tmpNode = tmpNode.next
		if tmpNode.val != nil {
			builder.WriteString(strconv.Itoa(tmpNode.val.(int)))
		}

	}
	return builder.String()
}
